home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 12 / BBS in a box XII-1.iso / Files / Unstuffers / Other Compression / MacGzip 0.21-src-c.sit / macgzip_021-src / unpack.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-08  |  8.0 KB  |  245 lines  |  [TEXT/KAHL]
  1. /* unpack.c -- decompress files in pack format.
  2.  * Copyright (C) 1992-1993 Jean-loup Gailly
  3.  * This is free software; you can redistribute it and/or modify it under the
  4.  * terms of the GNU General Public License, see the file COPYING.
  5.  */
  6.  
  7. /*
  8.  * Modified:1993 by SPDsoft for MacGzip
  9.  *
  10.  */
  11.  
  12. #ifdef RCSID
  13. static char rcsid[] = "$Id: unpack.c,v 1.4 1993/06/11 19:25:36 jloup Exp $";
  14. #endif
  15.  
  16. #include "tailor.h"
  17. #include "gzip.h"
  18. #include "crypt.h"
  19.  
  20. #define MIN(a,b) ((a) <= (b) ? (a) : (b))
  21. /* The arguments must not have side effects. */
  22.  
  23. #define MAX_BITLEN 25
  24. /* Maximum length of Huffman codes. (Minor modifications to the code
  25.  * would be needed to support 32 bits codes, but pack never generates
  26.  * more than 24 bits anyway.)
  27.  */
  28.  
  29. #define LITERALS 256
  30. /* Number of literals, excluding the End of Block (EOB) code */
  31.  
  32. #define MAX_PEEK 12
  33. /* Maximum number of 'peek' bits used to optimize traversal of the
  34.  * Huffman tree.
  35.  */
  36.  
  37. local ulg orig_len;       /* original uncompressed length */
  38. local int max_len;        /* maximum bit length of Huffman codes */
  39.  
  40. local uch literal[LITERALS];
  41. /* The literal bytes present in the Huffman tree. The EOB code is not
  42.  * represented.
  43.  */
  44.  
  45. local int lit_base[MAX_BITLEN+1];
  46. /* All literals of a given bit length are contiguous in literal[] and
  47.  * have contiguous codes. literal[code+lit_base[len]] is the literal
  48.  * for a code of len bits.
  49.  */
  50.  
  51. local int leaves [MAX_BITLEN+1]; /* Number of leaves for each bit length */
  52. local int parents[MAX_BITLEN+1]; /* Number of parents for each bit length */
  53.  
  54. local int peek_bits; /* Number of peek bits currently used */
  55.  
  56. /* local uch prefix_len[1 << MAX_PEEK]; */
  57. #define prefix_len outbuf
  58. /* For each bit pattern b of peek_bits bits, prefix_len[b] is the length
  59.  * of the Huffman code starting with a prefix of b (upper bits), or 0
  60.  * if all codes of prefix b have more than peek_bits bits. It is not
  61.  * necessary to have a huge table (large MAX_PEEK) because most of the
  62.  * codes encountered in the input stream are short codes (by construction).
  63.  * So for most codes a single lookup will be necessary.
  64.  */
  65. #if (1<<MAX_PEEK) > OUTBUFSIZ
  66.     error cannot overlay prefix_len and outbuf
  67. #endif
  68.  
  69. local ulg bitbuf;
  70. /* Bits are added on the low part of bitbuf and read from the high part. */
  71.  
  72. local int valid;                  /* number of valid bits in bitbuf */
  73. /* all bits above the last valid bit are always zero */
  74.  
  75. /* Set code to the next 'bits' input bits without skipping them. code
  76.  * must be the name of a simple variable and bits must not have side effects.
  77.  * IN assertions: bits <= 25 (so that we still have room for an extra byte
  78.  * when valid is only 24), and mask = (1<<bits)-1.
  79.  */
  80. #define look_bits(code,bits,mask) \
  81. { \
  82.   while (valid < (bits)) bitbuf = (bitbuf<<8) | (ulg)get_byte(), valid += 8; \
  83.   code = (bitbuf >> (valid-(bits))) & (mask); \
  84. }
  85.  
  86. /* Skip the given number of bits (after having peeked at them): */
  87. #define skip_bits(bits)  (valid -= (bits))
  88.  
  89. #define clear_bitbuf() (valid = 0, bitbuf = 0)
  90.  
  91. /* Local functions */
  92.  
  93. local void read_tree  OF((void));
  94. local void build_tree OF((void));
  95.  
  96. /* ===========================================================================
  97.  * Read the Huffman tree.
  98.  */
  99. local void read_tree()
  100. {
  101.     int len;  /* bit length */
  102.     int base; /* base offset for a sequence of leaves */
  103.     int n;
  104.  
  105.     /* Read the original input size, MSB first */
  106.     orig_len = 0;
  107.     for (n = 1; n <= 4; n++) orig_len = (orig_len << 8) | (ulg)get_byte();
  108.  
  109.     max_len = (int)get_byte(); /* maximum bit length of Huffman codes */
  110.     if (max_len > MAX_BITLEN) {
  111.     error("invalid compressed data -- Huffman code > 32 bits");
  112.     }
  113.  
  114.     /* Get the number of leaves at each bit length */
  115.     n = 0;
  116.     for (len = 1; len <= max_len; len++) {
  117.     leaves[len] = (int)get_byte();
  118.     n += leaves[len];
  119.     }
  120.     if (n > LITERALS) {
  121.     error("too many leaves in Huffman tree");
  122.     }
  123.     Trace((stderr, "orig_len %ld, max_len %d, leaves %d\n",
  124.        orig_len, max_len, n));
  125.     /* There are at least 2 and at most 256 leaves of length max_len.
  126.      * (Pack arbitrarily rejects empty files and files consisting of
  127.      * a single byte even repeated.) To fit the last leaf count in a
  128.      * byte, it is offset by 2. However, the last literal is the EOB
  129.      * code, and is not transmitted explicitly in the tree, so we must
  130.      * adjust here by one only.
  131.      */
  132.     leaves[max_len]++;
  133.  
  134.     /* Now read the leaves themselves */
  135.     base = 0;
  136.     for (len = 1; len <= max_len; len++) {
  137.     /* Remember where the literals of this length start in literal[] : */
  138.     lit_base[len] = base;
  139.     /* And read the literals: */
  140.     for (n = leaves[len]; n > 0; n--) {
  141.         literal[base++] = (uch)get_byte();
  142.     }
  143.     }
  144.     leaves[max_len]++; /* Now include the EOB code in the Huffman tree */
  145. }
  146.  
  147. /* ===========================================================================
  148.  * Build the Huffman tree and the prefix table.
  149.  */
  150. local void build_tree()
  151. {
  152.     int nodes = 0; /* number of nodes (parents+leaves) at current bit length */
  153.     int len;       /* current bit length */
  154.     uch *prefixp;  /* pointer in prefix_len */
  155.  
  156.     for (len = max_len; len >= 1; len--) {
  157.     /* The number of parent nodes at this level is half the total
  158.      * number of nodes at parent level:
  159.      */
  160.     nodes >>= 1;
  161.     parents[len] = nodes;
  162.     /* Update lit_base by the appropriate bias to skip the parent nodes
  163.      * (which are not represented in the literal array):
  164.      */
  165.     lit_base[len] -= nodes;
  166.     /* Restore nodes to be parents+leaves: */
  167.     nodes += leaves[len];
  168.     }
  169.     /* Construct the prefix table, from shortest leaves to longest ones.
  170.      * The shortest code is all ones, so we start at the end of the table.
  171.      */
  172.     peek_bits = MIN(max_len, MAX_PEEK);
  173.     prefixp = &prefix_len[1<<peek_bits];
  174.     for (len = 1; len <= peek_bits; len++) {
  175.     int prefixes = leaves[len] << (peek_bits-len); /* may be 0 */
  176.     while (prefixes--) *--prefixp = (uch)len;
  177.     }
  178.     /* The length of all other codes is unknown: */
  179.     while (prefixp > prefix_len) *--prefixp = 0;
  180. }
  181.  
  182. /* ===========================================================================
  183.  * Unpack in to out.  This routine does not support the old pack format
  184.  * with magic header \037\037.
  185.  *
  186.  * IN assertions: the buffer inbuf contains already the beginning of
  187.  *   the compressed data, from offsets inptr to insize-1 included.
  188.  *   The magic header has already been checked. The output buffer is cleared.
  189.  */
  190. int unpack(in, out)
  191.     int in, out;            /* input and output file descriptors */
  192. {
  193.     int len;                /* Bit length of current code */
  194.     unsigned eob;           /* End Of Block code */
  195.     register unsigned peek; /* lookahead bits */
  196.     unsigned peek_mask;     /* Mask for peek_bits bits */
  197.  
  198.     ifd = in;
  199.     ofd = out;
  200.  
  201.     read_tree();     /* Read the Huffman tree */
  202.     build_tree();    /* Build the prefix table */
  203.     clear_bitbuf();  /* Initialize bit input */
  204.     peek_mask = (1<<peek_bits)-1;
  205.  
  206.     /* The eob code is the largest code among all leaves of maximal length: */
  207.     eob = leaves[max_len]-1;
  208.     Trace((stderr, "eob %d %x\n", max_len, eob));
  209.  
  210.     /* Decode the input data: */
  211.     for (;;) {
  212.     /* Since eob is the longest code and not shorter than max_len,
  213.          * we can peek at max_len bits without having the risk of reading
  214.          * beyond the end of file.
  215.      */
  216.     look_bits(peek, peek_bits, peek_mask);
  217.     len = prefix_len[peek];
  218.     if (len > 0) {
  219.         peek >>= peek_bits - len; /* discard the extra bits */
  220.     } else {
  221.         /* Code of more than peek_bits bits, we must traverse the tree */
  222.         ulg mask = peek_mask;
  223.         len = peek_bits;
  224.         do {
  225.                 len++, mask = (mask<<1)+1;
  226.         look_bits(peek, len, mask);
  227.         } while (peek < (unsigned)parents[len]);
  228.         /* loop as long as peek is a parent node */
  229.     }
  230.     /* At this point, peek is the next complete code, of len bits */
  231.     if (peek == eob && len == max_len) break; /* end of file? */
  232.     put_ubyte(literal[peek+lit_base[len]]);
  233.     Tracev((stderr,"%02d %04x %c\n", len, peek,
  234.         literal[peek+lit_base[len]]));
  235.     skip_bits(len);
  236.     } /* for (;;) */
  237.  
  238.     flush_window();
  239.     Trace((stderr, "bytes_out %ld\n", bytes_out));
  240.     if (orig_len != (ulg)bytes_out) {
  241.     error("invalid compressed data--length error");
  242.     }
  243.     return OK;
  244. }
  245.